#include <bits\stdc++.h>

#include <iostream>
using namespace std;

void MatrixChain(int* p, int n, int** m,
                 int** s);  // 计算最优值，动态规划方法 p49
void Traceback(int i, int j, int** s);  // 构造最优解 p50
int RecurMatrixChain(
    int i, int j);  // 计算最优值，直接递归方法(会有大量的重复子问题) p51
int MemoizedMatrixChain(int n, int** m, int** s);  // 计算最优值，备忘录方法 p53
int LookupChain(int i, int j);
void DisplayMatrix(int** m, int n);  // 输出矩阵

// n个矩阵，需要n+1长度的数组存储行列信息
// 本实验中，数组0行和0列的部分都不使用，仅为便于理解
const int n = 6;
int p[n + 1 + 5] = {30, 35, 15, 5, 10, 20, 25};
int** m = new int*[n + 1];
int** s = new int*[n + 1];

// 矩阵连乘 p47
void matrixMultiPly(int** a, int** b, int** c, int ra, int ca, int rb, int cb) {
  if (ca != rb) {
    printf("矩阵不可连乘");
  }
  for (int i = 0; i < ra; i++) {
    for (int j = 0; j < cb; j++) {
      int sum = a[i][0] * b[0][j];
      for (int k = 1; k < ca; k++) {
        sum += a[i][k] * b[k][j];
      }
      c[i][j] = sum;
    }
  }
}
// 计算最优值，动态规划方法 p49
void MatrixChain(int* p, int n, int** m, int** s) {
  for (int i = 1; i <= n; i++) {
    m[i][i] = 0;
  }
  for (int r = 2; r <= n; r++) {
    for (int i = 1; i <= n - r + 1; i++) {
      int j = i + r - 1;
      // m[i:j]划分为m[i:i]和m[i+1:j]
      m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];
      s[i][j] = i;
      for (int k = i + 1; k < j; k++) {
        // m[i:j]划分为m[i:k]和m[k+1:j]
        int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
        if (t < m[i][j]) {
          m[i][j] = t;
          s[i][j] = k;
        }
      }
    }
  }
}
// 构造最优解 p50
void Traceback(int i, int j, int** s) {
  if (i == j) return;
  Traceback(i, s[i][j], s);
  Traceback(s[i][j] + 1, j, s);
  cout << "Multiply A " << i << "," << s[i][j];
  cout << " and A " << (s[i][j] + 1) << "," << j << endl;
}

// 计算最优值，直接递归方法(会有大量的重复子问题) p51
int RecurMatrixChain(int i, int j) {
  if (i == j) {
    return 0;
  }
  // m[i:j]划分为m[i:i]和m[i + 1:j]
  int u = RecurMatrixChain(i, j) + RecurMatrixChain(i + 1, j) +
          p[i - 1] * p[i] * p[j];
  s[i][j] = 1;
  for (int k = i + 1; k < j; k++) {
    // m[i:j]划分为m[i:k]和m[k + 1:j]
    int t = RecurMatrixChain(i, k) + RecurMatrixChain(k + 1, j) +
            p[i - 1] * p[k] * p[j];
    if (t < u) {
      u = t;
      s[i][j] = k;
    }
  }
  return u;
}

// 计算最优值，备忘录方法 p53
int MemoizedMatrixChain(int n, int** m, int** s) {
  // 初始化m，0表示没有计算过
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      m[i][j] = 0;
    }
  }
  return LookupChain(1, n);
}
int LookupChain(int i, int j) {
  if (m[i][j] > 0) {  //如果已经计算过，直接返回值
    return m[i][j];
  }
  if (i == j) {
    return 0;
  }
  // 没有计算过，递归的去计算每一种划分方式对应的值，找出最优值并记录对应的组合方式
  int u = LookupChain(i, i) + LookupChain(i + 1, j) + p[i - 1] * p[i] * p[j];
  s[i][j] = i;
  for (int k = i + 1; k < j; k++) {
    int t = LookupChain(i, k) + LookupChain(k + 1, j) + p[i - 1] * p[k] * p[j];
    if (t < u) {
      u = t;
      s[i][j] = k;
    }
  }
  m[i][j] = u;  // 保存最优值
  return u;
}

// 输出一个n*n的矩阵
void DisplayMatrix(int** m, int n) {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      printf("%d\t", m[i][j]);
    }
    printf("\n");
  }
}

int main() {
  // 初始化二维数组
  for (int i = 0; i < n + 1; i++) {
    m[i] = new int[n + 1];
    s[i] = new int[n + 1];
    // 为数组赋初始值为0
    memset(m[i], 0, sizeof(int) * (n + 1));
    memset(s[i], 0, sizeof(int) * (n + 1));
  }

  printf("动态规划方法：\n");
  MatrixChain(p, n, m, s);
  printf("m：\n");
  DisplayMatrix(m, n);
  printf("s：\n");
  DisplayMatrix(m, n);
  printf("最优解：\n");
  Traceback(1, n, s);

  printf("备忘录方法：\n");
  MemoizedMatrixChain(n, m, s);
  // 此方式首先会初始化 m内的值，所以此处不手动重置，不会影响结果
  printf("m：\n");
  DisplayMatrix(m, n);
  printf("s：\n");
  DisplayMatrix(m, n);
  printf("最优解：\n");
  Traceback(1, n, s);
  return 0;
}
